#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //双指针
    vector<int>ans1(vector<int>& nums, int target){
        int len = nums.size();
        vector<int> ret;
        for(int i = 0; i != len; i++){
            int p = i+1;
            while(p < len){
                if(nums[i] + nums[p] == target){
                    ret.push_back(i);
                    ret.push_back(p);
                    break;
                }
                p++;
            }
        }
        return ret;
    }

    //哈希表（find）
    vector<int>ans2(vector<int>& nums, int target){
        unordered_map<int, int> map;
        for(int i = 0; i != nums.size(); i++){
            auto it = map.find(target - nums[i]);
            if(it != map.end()){
                return {it->second, i};
            }
            map[nums[i]] = i;
        }
        return {};
    }
};

void test1(){
    Solution s;
    vector<int> nums = {2,7,11,15};
    int target = 9;
    // vector<int> ret = s.ans1(nums, target);
    vector<int> ret = s.ans2(nums, target);
    cout << ret[0] << ", " << ret[1] << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {3,2,4};
    int target = 6;
    // vector<int> ret = s.ans1(nums, target);
    vector<int> ret = s.ans2(nums, target);
    cout << ret[0] << ", " << ret[1] << endl;
}

void test3(){
    Solution s;
    vector<int> nums = {3,3};
    int target = 6;
    // vector<int> ret = s.ans1(nums, target);
    vector<int> ret = s.ans2(nums, target);
    cout << ret[0] << ", " << ret[1] << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}